package com.leetcode.binarytree;

import com.leetcode.datastructure.TreeNode;
import org.junit.Test;

/**
 * @author: ZhouBert
 * @date: 2019/10/31
 * @description: 112. 路径总和
 * 给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
 * 说明: 叶子节点是指没有子节点的节点。
 */
public class PathSum112A {

	/**
	 * 遍历求和
	 *
	 * @param root
	 * @param sum
	 * @return
	 */
	public boolean hasPathSum(TreeNode root, int sum) {
		if (root == null) {
			return false;
		}
		if (root.left == null && root.right == null) {
			return sum == root.val;
		}
		return hasPathSumRecursive(root, sum, 0);

	}

	/**
	 * 1ms	97.8
	 * @param root
	 * @param sum
	 * @param tempSum
	 * @return
	 */
	public boolean hasPathSumRecursive(TreeNode root, int sum, int tempSum) {
		//如果不是叶子节点，直接返回false
		if (root == null) {
			return false;
		}
		///todo:当叶子节点时，需要计算该叶子节点的权
		if (root.left == null && root.right == null) {
//			return sum == (tempSum+root.val);
			System.out.println(tempSum+root.val);
			return sum == (tempSum+root.val);
		}
		return hasPathSumRecursive(root.left, sum, tempSum + root.val) || hasPathSumRecursive(root.right, sum, root.val + tempSum);
	}

	@Test
	public void testHashPath() {
		TreeNode node = TreeNode.stringToTreeNode("[5,4,8,11,null,13,4,7,2,null,null,null,1]");
		System.out.println(hasPathSum(node, 22));
	}

}
